package com.hr.剑指offer.work1;

/**
 * @author 周恒哲
 * @date 2020/06/17
 **/
public class 面试题24_反转链表 {
    //递归
    public ListNode reverseList(ListNode head) {
        //递归终止条件：当前为空，或者下一个节点为空
        if (head==null||head.next==null){
            return head;
        }
        //递归调用来反转每一个节点
        ListNode cur = reverseList(head.next);
        //每一个节点如何反转
        head.next.next=head;
        //防止聊表循环，需要将head.next设置为空
        head.next=null;
        return cur;
    }
    //双指针
    public ListNode reverseList2(ListNode head) {
        //申请节点，pre和 cur，pre指向null
        ListNode pre=null;
        ListNode cur=head;
        ListNode tmp=null;
        while (cur!=null){
            //记录当前节点的下一个节点
            tmp=cur.next;
            //然后将当前节点指向pre
            cur.next=pre;
            //pre和cur节点都前进一位
            pre=cur;
            cur=tmp;
        }
        return pre;
    }
}
